/*
 * Copyright (C), 2015-2018
 * FileName: Solution088
 * Author:   zhao
 * Date:     2018/9/7 11:41
 * Description: 88. 合并两个有序数组
 * History:
 * <author>          <time>          <version>          <desc>
 * 作者姓名           修改时间           版本号              描述
 */
package com.lizhaoblog.hundredone;

/**
 * 〈一句话功能简述〉<br>
 * 〈88. 合并两个有序数组〉
 *
 * @author zhao
 * @date 2018/9/7 11:41
 * @since 1.0.1
 */
public class Solution088 {
  /**************************************
   * 题目


   给定两个有序整数数组 nums1 和 nums2，将 nums2 合并到 nums1 中，使得 num1 成为一个有序数组。

   说明:

   初始化 nums1 和 nums2 的元素数量分别为 m 和 n。
   你可以假设 nums1 有足够的空间（空间大小大于或等于 m + n）来保存 nums2 中的元素。
   示例:

   输入:
   nums1 = [1,2,3,0,0,0], m = 3
   nums2 = [2,5,6],       n = 3

   输出: [1,2,2,3,5,6]
   **************************************/

  /**************************************
   *
   * 想法：
   *
   * 我的做法
   * 超过88.68%的测试案例
   * 总结：
   *
   * ***********************************/
  public void merge(int[] nums1, int m, int[] nums2, int n) {
    // 总数索引、更新mn为索引
    int sum = m + n;
    m--;
    n--;
    sum--;

    // 循环mn，从后面往前循环，比较最大值，并将值填到该在的位置
    while (m > -1 && n > -1) {
      if (nums1[m] > nums2[n]) {
        nums1[sum] = nums1[m];
        m--;
      } else {
        nums1[sum] = nums2[n];
        n--;
      }
      sum--;
    }

    // 当m、n其中一个数组遍历完成后，这时候没办法比较
    // m不用重新填值了
    // n数组需要重新填值
    while (n > -1) {
      nums1[sum] = nums2[n];
      sum--;
      n--;
    }
  }

  /**************************************
   * 比我好的答案
   * ***********************************/
  public void better(int[] nums1, int m, int[] nums2, int n) {
    int[] nums = new int[m + n];
    int index = 0;
    int i = 0;
    int j = 0;
    while (i < m && j < n) {
      if (nums1[i] <= nums2[j]) {
        nums[index++] = nums1[i++];
      } else {
        nums[index++] = nums2[j++];
      }
    }

    while (i < m) {
      nums[index++] = nums1[i++];
    }
    while (j < n) {
      nums[index++] = nums2[j++];
    }

    System.arraycopy(nums, 0, nums1, 0, nums.length);

  }
}
